#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INCREATMENT 10
#define MAX_SIZE 100
typedef int Status;

typedef struct posType // 存放坐标位置
{
    int x;
    int y;
} posType;

typedef struct ElemType
{
    int ord;            // 通道块在路径的序号
    struct posType pos; // 坐标
    int di;             // 向下一块走的方向(1,2,3,4分别代表上下左右)
} SElemType;

typedef struct SqStack
{
    SElemType *base;
    SElemType *top;
    int stacksize;
} SqStack;

Status InitStack(SqStack *stack) // 初始化
{
    stack->base = (SElemType *)malloc(sizeof(SElemType) * MAX_SIZE);
    stack->stacksize = MAX_SIZE;
    stack->top = stack->base;
    return OK;
}

void show_maze(int maze[][10], int row, int col)
{
    for (int i = 0; i < col; i++)
    {
        for (int j = 0; j < row; j++)
        {
            if (maze[i][j] == 1)
            {
                printf("-");
            }
            else
            {
                printf("x");
            }
        }
        printf("\n");
    }
}

Status push(SqStack *stack, SElemType *e)
{
    if (stack->top - stack->base >= stack->stacksize)
    { // 栈满，追加空间
        stack->base = (SElemType *)realloc(stack->base, (stack->stacksize + STACK_INCREATMENT) * sizeof(SElemType));
        stack->top = stack->base + stack->stacksize;
        stack->stacksize += STACK_INCREATMENT;
    }
    stack->top++;
    *(stack->top) = *e;
    return OK;
}

Status is_empty(SqStack *stack)
{
    if (stack->top == stack->base)
    {
        return TRUE;
    }
    return FALSE;
}

Status pop(SqStack *stack, SElemType *e)
{
    if (stack->top == stack->base)
    {
        return ERROR;
    }
    *e = *(stack->top);
    stack->top--;
    return OK;
}

Status Get_top(SqStack *stack, SElemType *e)
{
    if (stack->top == stack->base)
    {
        return ERROR;
    }
    else
    {
        *e = *(stack->top);
    }
    return OK;
}

void path_finding(SqStack *stack, int maze[][10], posType *outer)
{
    while (is_empty(stack) != 1) // 栈不空循环
    {
        SElemType *this_e = (SElemType *)malloc(sizeof(SElemType));
        Get_top(stack, this_e);
        int i = this_e->pos.x;
        int j = this_e->pos.y;
        int find = 0;
        int di = this_e->di;
        int a, b;
        if (i == outer->x && j == outer->y) // 找到出口输出该路径
        {
            // printf("%d %d----\n", i, j);
            break;
        }
        // else
        // {
        //     // printf("%d %d-----\n", i, j);
        // }

        while (di < 4 && !find) // 找下一个可走方块
        {
            di++;       // 初值为-1
            switch (di) // 试探方块
            {
            case 0: // 上
                a = i - 1, b = j;
                break;
            case 1: // 右
                a = i, b = j + 1;
                break;
            case 2: // 下
                a = i + 1, b = j;
                break;
            case 3: // 左
                a = i, b = j - 1;
                break;
            }
            if (maze[a][b] == 1)
                find = 1; // 找到可走方块(a,b)
        }

        if (find == 1) // 找到
        {
            (*stack).top->di = di;
            this_e->pos.x = a;
            this_e->pos.y = b;
            this_e->di = -1;
            push(stack, this_e); // 方块（a，b）入栈
            maze[a][b] = -1;     // 设为-1防止重复走
        }
        else // 找不到
        {
            SElemType *temp_e = (SElemType *)malloc(sizeof(SElemType));
            pop(stack, temp_e);
            maze[temp_e->pos.x][temp_e->pos.y] = 1; // 恢复退栈方块
        }
    }
}
int main() // 迷宫寻路,只寻找一个就可以
{
    // 构建迷宫
    int maze[10][10] =
        {
            //  0, 1, 2, 3 ,4 ,5, 6 ,7 ,8, 9
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 0
            {0, 1, 1, 0, 1, 1, 1, 0, 1, 0}, // 1
            {0, 1, 1, 0, 1, 1, 1, 0, 1, 0}, // 2
            {0, 1, 1, 1, 1, 0, 0, 1, 1, 0}, // 3
            {0, 1, 0, 0, 0, 1, 1, 1, 1, 0}, // 4
            {0, 1, 1, 1, 0, 1, 1, 1, 1, 0}, // 5
            {0, 1, 0, 1, 1, 1, 0, 1, 1, 0}, // 6
            {0, 1, 0, 0, 0, 1, 0, 0, 1, 0}, // 7
            {0, 0, 1, 1, 1, 1, 1, 1, 1, 0}, // 8
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}  // 9
        };

    // 其中0代表不可通,1代表可通
    SqStack *stack = (SqStack *)malloc(sizeof(SqStack)); // 设置栈
    InitStack(stack);

    posType *outer = (posType *)malloc(sizeof(posType)); // 定义出口
    outer->x = 8;
    outer->y = 8;

    SElemType *entry = (SElemType *)malloc(sizeof(SElemType)); // 定义入口
    entry->pos.x = 1;
    entry->pos.y = 1;
    entry->di = -1;
    entry->ord = 1;

    // 首先把入口压栈
    push(stack, entry);

    // 查看迷宫
    show_maze(maze, 10, 10);

    // 寻路函数
    path_finding(stack, maze, outer);
    printf("寻路完成,一条路径如下:\n");

    // 输出结果
    SElemType *e = (SElemType *)malloc(sizeof(SElemType));
    while (is_empty(stack) != 1)
    {
        pop(stack, e);
        printf("坐标:%d  %d\n", e->pos.x, e->pos.y);
    }

    return 0;
}